package leetcode_top;
import java.util.*;
import org.junit.*;

public class Ex224 {
    class Solution {
        public int calculate(String s) {
            char c;
            if ((c = s.charAt(0)) == '+' || c == '-')
                s = "0" + s;

            s = s.replaceAll(" ", "");
            s = s.replace("(+","(0+");
            s = s.replace("(-", "(0-");
            s = s.replaceAll("\\-\\-", "+"); 
            s = s.replaceAll("\\+\\-", "-"); 
            s = s.replaceAll("\\-\\+", "-"); 
            s = s.replaceAll("\\+\\+", "+"); 

            char[] cs = s.toCharArray();
            int last = 0, j, len = cs.length, a, b;
            Map<Character, Integer> map = new HashMap<>();
            map.put('+', 1);
            map.put('-', 1);
            map.put('*', 2);
            map.put('/', 2);
            map.put('(', 0);
            Stack<Integer> nums = new Stack<>();
            Stack<Character> ops = new Stack<>();
            for (int i = 0; i < len; i++) {
                c = cs[i];
                if (isDigit(c)) {
                    j = i;
                   while (j < len && isDigit(cs[j])) {
                        last = last * 10 + cs[j++] - '0';
                   }
                   i = j - 1;
                   nums.push(last);
                   last = 0;
                } else {
                    if (c == '(' || ops.isEmpty()) {
                        ops.push(c);
                    } else if (c == ')') {
                        char t;
                        while (ops.peek() != '(') {
                            t = ops.pop();
                            b = nums.pop();
                            a = nums.pop();
                            nums.push(calc(t, a, b));
                        }
                        ops.pop();
                    } else {
                        char t;
                        //若优先级大于栈顶，不会走这个while
                        while (!ops.isEmpty() &&  map.get(c) <= map.get(ops.peek())) {
                            t = ops.pop();
                            b = nums.pop();
                            a = nums.pop();
                            nums.push(calc(t, a, b));
                        }
                        ops.push(c);
                    }
                }
            }

            while (!ops.isEmpty()) {
                char t = ops.pop();
                b = nums.pop();
                a = nums.pop();
                nums.push(calc(t, a, b));
            }

            return nums.peek();
        }

        private int calc(char t, int a, int b) {
            switch (t) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    return a / b;
                default:
                    System.out.println("不支持的运算符");
            }
            return -1;
        }

        public boolean isDigit(char c)  {
            return c >= '0' && c <= '9';
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.calculate("-2+ 1"));        
    }
}
